Fritz John conditions

The Fritz John conditions (abbr. FJ conditions), in mathematics, are a necessary condition for a solution in nonlinear programming to be optimal. They are used as lemma in the proof of the Karush–Kuhn–Tucker conditions.

We consider the following optimization problem:


\begin{align}
    \text{minimize } & f(x) \, \\
    \text{subject to: } & g_i(x) \ge 0,\ i \in \left \{1,\dots,m \right \}\\
        & h_j(x) = 0, \ j \in \left \{m%2B1,\dots,n \right \}
\end{align}

where ƒ is the function to be minimized, g_i the inequality constraints and h_j the equality constraints, and where, respectively, \mathcal{I}, \mathcal{I'} and \mathcal{E} are the indices set of inactive, active and equality constraints and x^* is a optimal solution of f, then there exists a non-zero number \lambda _0 and a non-zero vector \lambda=[\lambda _1, \lambda _2,\dots,\lambda _n] such that:

 \begin{cases}
   \lambda_0 \nabla f(x^*) = \sum\limits_{i\in \mathcal{I}'} \lambda_i \nabla g_i(x^*) %2B \sum\limits_{i\in \mathcal{E}} \lambda_i \nabla h_i (x^*) \\[10pt]
   \lambda_i \ge 0,\  i\in \mathcal{I}' \\[10pt]
   \exists i\in \left( \{0,1,\ldots ,n\} \backslash \mathcal{I} \right) \left( \lambda_i \ne 0 \right)
\end{cases}

\lambda_0=0 iff the \nabla g_i (i\in\mathcal{I}') and \nabla h_i (i\in\mathcal{E}) are linearly dependent and \lambda_i\neq 0,\,\forall i\in\mathcal{I}'\cup\mathcal{E}, i.e. if the constraint qualifications do not hold.

Named after Fritz John, these conditions are equivalent to the Karush–Kuhn–Tucker conditions in the case \lambda_0 = 1.

References